#include <iostream>
#include <vector>
using namespace std;

class Solution {
	int can(vector<int> &nums, int k, int limit, int status, int sum, int cur, vector<int> &dp)
	{
		if (cur == k) {
			return true;
		}

		if (dp[status] != -1) {
			return dp[status];
		}

		for (int i = 0; i < nums.size(); i++) {
			if (status & (1 << i)) {
				if (sum + nums[i] < limit && can(nums, k, limit, status ^ (1 << i), sum + nums[i], cur, dp)) {
                                        return dp[status] = true;
				}
                                if(sum + nums[i] == limit && can(nums, k, limit, status ^ ( 1 << i), 0, cur + 1, dp)){
                                        return dp[status] = true;
                                }
			}
		}
                return dp[status] = false;
	}

    public:
	bool canPartitionKSubsets(vector<int> &nums, int k)
	{
		int sum = 0;
		for (auto v : nums) {
			sum += v;
		}

		if (sum % k) {
			return false;
		}

		int n = nums.size();
		int limit = sum / k;
		int status = (1 << (n + 1)) - 1;
                vector<int> dp(status + 1, -1);
                return can(nums, k, limit, status, 0, 0, dp);
	}
};

int main()
{
	vector<int> nums = {  1,2,3,4};
	int k = 3;
	cout << Solution().canPartitionKSubsets(nums, k) << endl;
	return 0;
}